class Solution:
    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:
        q = deque([(0, 0)])
        ans = 0

        while q:
            person, step = q.popleft()
            if step == k:
                if person == n - 1:
                    ans += 1
                continue
            
            for ways in relation:
                if ways[0] == person:
                    q.append(way[1], step + 1)

        return ans
